Chào mừng đến với Bài 3 của Khái niệm Trí tuệ Nhân tạo (PolyU COMP5511). Trong buổi học này, chúng ta chuyển từ tìm đường cho một tác tử sang Tìm kiếm Đối kháng, nơi các tác tử hoạt động trong môi trường đa tác tử cạnh tranh. Chúng ta cũng giới thiệu Bài toán Thỏa mãn Ràng buộc (CSPs), một mô hình trong đó mục tiêu là tìm một trạng thái thỏa mãn một tập hợp các ràng buộc cụ thể thay vì tìm một đường đi.
Các Khái niệm Cốt lõi
- Tìm kiếm Đối kháng: Tập trung vào các thuật toán như Minimax và Cắt tỉa Alpha-Beta để đưa ra quyết định hợp lý khi đối đầu với một đối thủ thông minh.
- Tìm kiếm Cây Monte Carlo (MCTS): Khám phá việc ra quyết định theo xác suất, đóng vai trò là nền tảng cho các AI chơi game hiện đại như AlphaGo.
- Thỏa mãn Ràng buộc: Mô hình hóa bài toán bằng Biến, Miền giá trị và Ràng buộc, được giải bằng Quay lui và Tìm kiếm Cục bộ.
Phân tích Độ phức tạp
Trong các bối cảnh đối kháng, độ phức tạp của không gian tìm kiếm thường được xác định bởi hệ số phân nhánh của trò chơi
Cảnh báo Chuyển đổi Mô hình
Không giống như tìm kiếm tiêu chuẩn (ví dụ: A* hoặc BFS) nơi môi trường là tĩnh, Tìm kiếm Đối kháng giả định rằng môi trường (đối thủ) chủ động cố gắng giảm thiểu thành công của bạn. Trong CSPs, thứ tự của các hành động ít quan trọng hơn tính hợp lệ của phép gán cuối cùng.
Mã giả Khái niệm: Các Loại Tác tử
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).